package demo2;

import java.util.Scanner;

public class MaxSubarraySum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("请输入数组元素个数 n: ");
        int n = scanner.nextInt();
        int[] arr = new int[n];
        System.out.println("请输入 " + n + " 个整数:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        int[] result = maxSubarraySum(arr);
        System.out.println("最大子段和: " + result[0]);
        System.out.println("起始下标: " + result[1]);
        System.out.println("终止下标: " + result[2]);

        scanner.close();
    }

    public static int[] maxSubarraySum(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];
        dp[0] = arr[0];
        int maxSum = dp[0];
        int start = 0;  // 起始下标
        int end = 0;    // 终止下标
        int tempStart = 0;  // 临时起始下标


        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(arr[i], dp[i - 1] + arr[i]);
            if (dp[i] == arr[i]) {
                tempStart = i;
            }

            // 更新全局最大值和下标
            if (dp[i] > maxSum) {
                maxSum = dp[i];
                start = tempStart;
                end = i;
            }
        }

        return new int[]{maxSum, start, end};
    }
}